package mytest.huaweiG.GraphB;

import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * Created by safe on 2017-04-01.
 */
class TimeRecorder {
    private int time = 0;

    public int getTime() {
        return time;
    }

    public void setTime(int time) {
        this.time = time;
    }


    public static Vertex[] topologicalSort(Graph graph) {
        Set<Vertex> vertexSet = graph.getVertexSet();
        if (vertexSet.size() < 2) {
            return vertexSet.toArray(new Vertex[0]);
        }

        LinkedList<Vertex> sortedList = new LinkedList<Vertex>();
        TimeRecorder recorder = new TimeRecorder();

        for (Vertex vertex : vertexSet) {
            if (vertex.getColor() == Color.WHITE) {
                visitVertex(graph, vertex, recorder, sortedList);
            }
        }

        return sortedList.toArray(new Vertex[0]);
    }

    /**
     * 深度优先搜索(Depth First Search)
     */
    public static void visitVertex(Graph graph, Vertex vertex,
                                   TimeRecorder recorder, LinkedList<Vertex> sortedList) {
        recorder.time += 1;
        vertex.setColor(Color.GRAY);
        vertex.setDiscover(recorder.time);

        Map<Vertex, Vertex[]> edgeMap = graph.getAdjacencys();
        Vertex[] adjacencys = edgeMap.get(vertex);
        if (adjacencys != null && adjacencys.length > 0) {
            for (Vertex adjacency : adjacencys) {
                if (adjacency.getColor() == Color.WHITE) {
                    adjacency.setParent(vertex);
                    visitVertex(graph, adjacency, recorder, sortedList);
                }
            }
        }

        recorder.time += 1;
        vertex.setColor(Color.BLACK);
        vertex.setFinish(recorder.time);
        sortedList.addLast(vertex);
    }
}